#include <iostream>
#include  <queue>

using namespace std;

typedef struct Bnode
{
	char data;
      struct Bnode * lchild, *rchild;
}Bnode, *Btree;

void Createtree(Btree &T)
{
    char ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
	    T = new Bnode;
   	    T->data = ch;
 	    Createtree(T->lchild);
        Createtree(T->rchild);
    }
}

void preorder(Btree T)
{
    if (T)
    {
        cout << T->data;
        preorder(T->lchild);
        preorder(T->rchild);
    }
}

void inorder(Btree T)
{
    if (T)
    {     
        inorder(T->lchild);
        cout << T->data;
        inorder(T->rchild);
    }
}

void posorder(Btree T)
{
    if (T)
    {     
        posorder(T->lchild);
        posorder(T->rchild);
        cout << T->data;
    }
}

bool Leveltraverse(Btree T)
{
    Btree p;
    if (!T))
        return false;
    queue<Btree> Q;
    Q.push(T);   //根指针入队
    while(!Q.empty())
    {
        p = Q.front();
        Q.pop();
        cout<<p->data << " ";
        if (p->lchild)
        {
            Q.push(p->lchild); //左孩子入队
        }

        if (p->rchild)
        {
            Q.push(p->rchild);//右孩子入队
        }
    }
}